package com.yoshino.leetcode.interview150.multidynamic;

import java.util.List;

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        // 从下到上遍历
        int n = triangle.size();
        int[] ress = new int[n];
        int i = 0;
        for (int cur: triangle.get(n - 1)) {
            ress[i++] = cur;
        }
        for (i = n - 2; i >= 0; i--) {
            int j = 0;
            for (int cur : triangle.get(i)) {
                ress[j] = Math.min(ress[j], ress[j + 1]) + cur;
                j++;
            }
        }
        return ress[0];
    }

    public int minPathSum(int[][] grid) {
        // 搞定边界，再进入内部
        int m = grid.length, n = grid[0].length;
        for (int i = 1; i < m; i++) {
            grid[i][0] += grid[i - 1][0];
        }
        for (int i = 1; i < n; i++) {
            grid[0][i] += grid[0][i - 1];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        return grid[m - 1][n - 1];
    }
}